After understanding Quick Sort's high-level divide-and-conquer approach, we now focus on its core mechanism: the Partitioning step, which must execute in-place to be efficient.

  • The goal of partitioning is to take a pivot element and place it in its final, sorted position, with all smaller elements to its left and all larger elements to its right.
  • Pivot Selection: For simplicity, we often choose the last element, A[high], as the pivot.
  • Index `i` (Small Boundary): This pointer tracks the boundary of the partition containing elements smaller than the pivot. Elements to the left of `i` are guaranteed to be $ \leq $ Pivot.
  • Index `j` (Iterator): This pointer iterates through the array from low to high-1, comparing each element A[j] against the pivot.
  • If A[j] is less than or equal to the pivot, we increment i and swap A[i] with A[j], effectively expanding the "smaller elements" partition.
  • After the loop finishes, the pivot is swapped into position i+1, completing the partition step.
Python Implementation: partition
1def partition(A, low, high):
2    # 1. Select the pivot (last element)
3    pivot = A[high]
4    
5    # 2. i is the index of the smaller element
6    i = low - 1
7
8    # 3. Iterate j from low to high-1
9    for j in range(low, high):
10        # If current element is smaller than or equal to pivot
11        if A[j] <= pivot:
12            # Move boundary i and swap A[i] and A[j]
13            i = i + 1
14            A[i], A[j] = A[j], A[i]
15    
16    # 4. Place the pivot in its final position (i + 1)
17    A[i + 1], A[high] = A[high], A[i + 1]
18    
19    # Return the partitioning index
20    return i + 1